A variety of detection algorithms are currently in use for extracting symbols from a digital telecommunication input. In general, the communication input that is to be analyzed may comprise one or more digital communication signals, each of which may include one or more data streams transmitted by one or more user devices. Each of the user devices may include one or more transmitters, and may transmit one or more data streams using one or more antennas.
For example, the digital communication input may include SU-MIMO (Single User-Multiple Input Multiple Output) data streams, where one user simultaneously sends multiple data streams using multiple transmit antennas that are received by multiple receive antennas. The data input may also include MU-MIMO (Multi User-Multiple Input Multiple Output) data streams, where multiple users simultaneously send multiple data streams using multiple transmit antennas that are received by multiple receive antennas. MUD (Multi-User Detection) is sometimes used as a generalized term, for modeling of multiple simultaneous data streams by the receiver, regardless of the number of users, transmit antennas, or receive antennas. In addition, the data streams may be transmitted using any of a number of transmission strategies, such as CDMA (Code Division Multiple Access), OFDM (Orthogonal Frequency Division Multiplexing), OFDMA (Orthogonal Frequency Division Multiple Access) and SC-FDMA (Single Carrier-Frequency Division Multiple Access).
For these transmission strategies, a maximum likelihood detector (“MLD”) detection algorithm provides the best performance in recognizing and extracting symbols from the digital communication input. This makes MLD a desirable choice for receiver detection algorithms. Any of several forms of MLD can be applied, depending on the detection requirements. For example, a Maximum Likelihood Sequence Detector (“MLSD”) can provide received data with the lowest average probability of bit errors, while a Maximum A-Posteriori Sequence Detector (“MAPSD”) can be used to minimize the individual probability of bit errors.
A simplified example of MLD is illustrated by the flow diagram of FIG. 1A. In this simplified example, an OFDMA data stream is received 100, and a Fourier transform 102 is applied. The symbols are then extracted by MLD 106, as is well understood in the art.
The fundamental strategy of MLD detection is to search over all possible combinations of transmit waveform sequences in order to find the combination that matches the received waveform most closely. Therefore it can be viewed as an exhaustive search over all combinations of how a received waveform could have been generated. The exhaustive search of the MLD detection algorithm often requires a significant amount of computing resources and/or time in order to perform the required calculations, because the number of required calculations can grow exponentially based on changes to various conditions. Therefore, many communication receivers use reduced complexity versions of the MLD, such as the sphere decoder or M-Algorithm, or lower performance, non-MLD based approaches such as linear techniques or successive interference cancellation.
SC-FDMA data streams (used for example in LTE uplinks) are especially challenging to process with MLD. In SC-FDMA, a series of symbols are spread in frequency by a Fast Fourier Transform (“FFT”) before being returned to the time domain by an inverse FFT (“iFFT”), where the iFFT size may be larger than the FFT size. The FFT spread causes the effect of a single symbol to be distributed over the entire time period that is associated with the iFFT. This typically provides a lower peak power to average power ratio, and allows user device transmitters to function more efficiently and allows use of transmitters having lower maximum power ratings.
A simplified example of SC-FDMA detection is illustrated by the flow diagram of FIG. 1B. In this simplified example, an SC-FDMA data stream is received 100, and a Fourier transform 102 is applied. A preprocessor 104 performs equalization and/or other operations on the transformed data, and then an inverse Fourier transform is applied 108. Finally, the symbols are extracted, typically by a simple demodulator since the signal has already been properly equalized by the preprocessor 104.
FIGS. 2A through 2D compare the OFDMA and SC-FDMA transmission strategies in terms of the distribution of the symbols in time and frequency during transmission. FIG. 2A illustrates QPSK modulating of the data symbols. FIG. 2B illustrates a sequence of transmitted QPSK symbols. FIG. 2C illustrates the symbols of FIG. 2B as they are distributed in time and frequency during transmission by OFDMA. Because a single inverse Fourier transform is applied before transmission, the symbols are concentrated in frequency and therefore extended in time. FIG. 2D illustrates the symbols of FIG. 2B as they are distributed in time and frequency during transmission by SC-FDMA. Because both a Fourier transform and an inverse Fourier transform are applied to the symbols before they are transmitted, the symbols are spread primarily in frequency, and are relatively concentrated in time, even though the energy from a single symbol does span the entire iFFT time window.
Due to the spreading of the symbols across all time, it is essentially impossible to process an SC-FDMA data stream using a full MLD algorithm. This is because the MLD search space would have to include all combinations of all possible symbols. As an example, for a 20 MHz LTE uplink including four 64-QAM data streams, an MLD algorithm would be required to perform 64^(4*1200) or 4.6×108669 operations. This is clearly infeasible, because the MLD detector would be required to perform this number of calculation every 66 microseconds, but in fact the most powerful supercomputer would not be able to perform this number of operations even if it started at the beginning of the known universe. Even a traditional, reduced complexity MLD, such as the sphere decoder or M-Algorithm, could not reduce the MLD complexity enough to make it a feasible detection method for SC-FDMA. Accordingly, extracting of symbols from multiple simultaneous SC-FDMA data streams has been limited to non-MLD detection algorithms, as illustrated in FIG. 1B.
What is needed, therefore, is a method and system for applying MLD detection to SC-FDMA data streams.